package P2分治回溯;

import java.util.LinkedList;

public class Hanoi {
    public static void main(String[] args) {
        String x = "x";
        String y = "y";
        String z = "z";
        hanoi(3, x, y, z);

        LinkedList<Integer> X = new LinkedList<>();
        for (int i = 3; i >= 1; i--) {
            X.push(i);
        }
        LinkedList<Integer> Y = new LinkedList<>();
        LinkedList<Integer> Z = new LinkedList<>();
        hanoi(3,X,Y,Z);
        System.out.println(Z);
    }
    private static void hanoi(int n, LinkedList begin, LinkedList mid, LinkedList end) {
        if (n == 1) {
            end.push(begin.pop());
        } else {
            hanoi(n - 1, begin, end, mid);
            end.push(begin.pop());
            hanoi(n - 1, mid, begin, end);
        }
    }
    private static void hanoi(int n, String begin, String mid, String end) {
        if (n == 1) {
            System.out.println(begin + "->" + end);
        } else {
            hanoi(n - 1, begin, end, mid);
            System.out.println(begin + "->" + end);
            hanoi(n - 1, mid, begin, end);
        }
    }
}